package tree.递归;

import po.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 从中序与后序遍历序列构造二叉树106.java
 * @Description TODO https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * @createTime 2021年03月27日 12:12:00
 */
public class 从中序与后序遍历序列构造二叉树106 {

    Map<Integer, Integer> map;
    int[] postOrder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        int postLength = postorder.length;
        int inLength = inorder.length;
        this.postOrder = postorder;
        map=new HashMap<>(inLength);
        for (int i = 0; i < inLength; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeRecurse(0, inLength - 1, 0, postLength - 1);
    }

    /**
     * [8 9 5]   [3]   [15 20 7]
     * is         in          ie
     * [8 5 9]   [15 7 20]   [3]
     * ps  pe'                pe
     */
    private TreeNode buildTreeRecurse(int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postEnd < postStart) {
            return null;
        }
        int rootVal = postOrder[postEnd];
        Integer rootIndex = map.get(rootVal);
        TreeNode treeNode=new TreeNode(rootVal);
        treeNode.left=buildTreeRecurse(inStart,rootIndex-1,postStart,postEnd-inEnd+rootIndex-1);
        treeNode.right=buildTreeRecurse(rootIndex+1,inEnd,postEnd-inEnd+rootIndex,postEnd-1);
        return treeNode;
    }
}
